package com.sicheng.蓝桥.练习题.dp;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/7 21:00
 */
public class 路径最短_dp {
    public static void main(String[] args) {
        long[] dp = new long[2022];

        for (int i = 1; i < 2022; i++) {
            for (int j = i + 1; j <= i + 21 && j < 2022; j++) {
                if (dp[j] == 0) {
                    dp[j] = dp[i] + i * j / gcd(i, j);
                } else
                    dp[j] = Math.min(dp[j], dp[i] + i * j / gcd(i, j));
            }
        }

        System.out.println(dp[2021]);

    }


    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
